package com.wtgroup.demo.mianshi.算法.etc;

import cn.hutool.core.collection.CollUtil;
import com.wtgroup.demo.common.bean.MultiTreeNode;
import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.Mock;
import lombok.AllArgsConstructor;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
import java.util.function.Consumer;
import java.util.function.Function;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/6 10:24
 */
public class D_递归改迭代 {

    public static void main(String[] args) {
        Judger.of(() -> {
            MultiTreeNode head = Mock.multiTree(10, 2);
            // MultiTreeNode head = Mock.multiTree(new int[]{720, -126, -279, 592}, 2);
            // System.out.println(head);

            List<MultiTreeNode> res1 = new ArrayList<>();
            List<MultiTreeNode> res2 = new ArrayList<>();

            doit_recurse(
                    head,
                    n -> {
                        res1.add(n);
                    },
                    nextsCnt -> 0 // 0 先序; (nextsCnt + 1) / 2 中序; nextsCnt 后序
            );
            doit_loop(
                    head,
                    n -> {
                        res2.add(n);
                    },
                    nextsCnt -> 0
            );

            // 对比 结果1 和 结果2
            boolean ret = CollUtil.isEqualList(res1, res2);
            if (!ret) {
                System.out.println(res1);
                System.out.println(res2);
            }


            return ret;
        }).setIterCount(1000).start().print();
    }

    /**
     * 树递归通用套路
     * @param head        树头结点
     * @param handle      节点处理逻辑. 比如遍历打印, 这里放打印逻辑即可
     * @param whenToHanle 何时处理. 0~分支个数, 0 所有分支前处理自身, 分支size 所有分支处理后处理自身.
     *                    入参: 分支索引(0开始)
     *                    出参: 处理自身的位置
     */
    static void doit_recurse(MultiTreeNode head, Consumer<MultiTreeNode> handle, Function<Integer, Integer> whenToHanle) {
        if (head == null) {
            return;
        }
        List<MultiTreeNode> nexts = head.getNexts();
        nexts = nexts == null ? new ArrayList<>() : nexts;

        if (nexts.size() == 0) {
            // 叶子节点, 前置后置处理取一个处理, 中间没有
            handle.accept(head);
            return;
        }

        Integer handleSelfPoint = whenToHanle.apply(nexts.size());

        // 先序处理自己
        if (handleSelfPoint == 0) {
            handle.accept(head);
        }

        // 分支处理
        for (int i = 0; i < nexts.size(); i++) {
            // 中间任意位置处理自身
            if (handleSelfPoint == i && handleSelfPoint != 0) { // 0 排除, 放上面好看些
                handle.accept(head);
            }

            MultiTreeNode next = nexts.get(i);
            doit_recurse(next, handle, whenToHanle);
        }

        if (handleSelfPoint == nexts.size()) {
            handle.accept(head);
        }
    }

    @AllArgsConstructor
    static class Frame {
        MultiTreeNode node;
    }

    /**
     *
     * @param head
     */
    // 递归改迭代的模板
    static void doit_loop_template(MultiTreeNode head) {
        /*
        首先, 递归, 想象成树的处理.
        如何想象成树? 单次递归里, 有几次子递归调用, 就是几叉树.
        1. 入参看情况封装到 Frame 中, 用于压栈,出栈, 记录运行时信息. 一个节点处都会对应一个 Frame
        2. 递归的 base case 原样放到循环内部, 执行完 continue .
        3. 遇到递归调用处, 观察当前 Frame 压过栈的分支偏移量(任务提交过了,处理过了). 总之, 灵活使用你的方式, 判断当前节点的所有子分支是否结束了
            3.1 达到分支个数, 说明, 所有子分支均已处理过, continue 下一轮迭代, 跳到 parent 处, 处理它的下一个子, 即我的后一个分支.
            3.2 否则, 自己压回栈中, 封装子节点处 Frame 压栈, 进入下一个子节点处处理.
        4. "自身" 处理, 原样放到循环内部对应位置.
         */
        // 异常数据处理

        Stack<Frame> stack = new Stack<>();
        stack.push(new Frame(head));
        Map<Frame, Integer> frameOffsetMap = new HashMap<>();

        while (!stack.isEmpty()) {
            Frame currFrame = stack.pop();
            // 1. base case , continue -- 递归的退出条件
            // if xxx:
            //  continue
            // --- ↑ continue -- 递归的退出条件 ---

            // 2. 择机调用处理器逻辑
            // 当前处理分支 和 指定调用的时机比较

            // 3. 当前节点的子分支处理完了, continue
            // if frameOffsetMap.get(currFrame) == nexts.size
            //   continue

            // 4. 否则, 自己压回栈中, 封装子节点处 Frame 压栈, 进入下一个子节点处处理. 并更新当前节点的子分支偏移量
        }
    }


    static void doit_loop(MultiTreeNode head, Consumer<MultiTreeNode> handle, Function<Integer, Integer> whenToHanle) {
        /*
        1. 入参看情况封装到 Frame 中, 用于压栈,出栈, 记录运行时信息. 一个节点处都会对应一个 Frame
        2. 递归的 base case 原样放到循环内部, 执行完 continue .
        3. 遇到递归调用处, 观察当前 Frame 压过栈的分支偏移量(任务提交过了,处理过了)
            3.1 达到分支个数, 说明, 所有子分支均已处理过, continue 下一轮迭代, 跳到 parent 处, 处理它的下一个子, 即我的后一个分支.
            3.2 否则, 自己压回栈中, 封装子节点处 Frame 压栈, 进入下一个子节点处处理.
        4. "自身" 处理, 原样放到循环内部对应位置.
         */

        if (head == null) {
            return;
        }

        // 当前节点子节点处理到的位置 == 压过栈的子节点Frame
        Map<Frame, Integer> frameOffsetMap = new HashMap<>();

        Stack<Frame> stack = new Stack<Frame>();
        stack.push(new Frame(head));

        while (stack.isEmpty() == false) {
            Frame currFrame = stack.pop();
            if (currFrame.node == null) {
                continue;
            }
            List<MultiTreeNode> nexts = currFrame.node.getNexts();
            nexts = nexts == null ? new ArrayList<>() : nexts;

            Integer lastHandlePoint = frameOffsetMap.get(currFrame);
            int currHandlePoint = lastHandlePoint == null ? 0 : lastHandlePoint + 1;
            Integer handleSelfPoint = whenToHanle.apply(nexts.size());

            // 自身处理逻位置刚好等于当前处理分支节点前, 就先把逻辑调用了, 然后, 下文才去处理分支节点. (前置处理器,中间处理器,后置处理器)
            if (handleSelfPoint == currHandlePoint) {
                handle.accept(currFrame.node);
            }

            if (currHandlePoint == nexts.size()) {
                continue;
            }

            // 1. 取出当前要处理的分支的节点 currHandlePoint
            MultiTreeNode currHandleChild = nexts.get(currHandlePoint);

            // 2 然后, 压栈
            stack.push(currFrame);
            stack.push(new Frame(currHandleChild));
            frameOffsetMap.put(currFrame, currHandlePoint);
        }

    }


}
